package primary.primary0;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 同题S1721直方图的水量
 */
public class S0042接雨水 {
    /**
     * 每个点能接的雨水，是 min(当前点左边的最大值,当前点右边的最大值)
     * 所有从左到右，从右到左遍历两遍就行
     * 不需要单调栈，只看最大值就行
     */


    /**
     * 答案
     * 递减栈也是可以的
     * 遍历到i，如果i比栈顶小，入栈
     * 也就是遍历到i的时候，i的前一个元素一定在栈顶的
     * 这里的栈相当于一截一截的拦水墙，栈中两个元素之间的区域都被淹没了右侧高度
     * 如果比栈顶大，逐个出栈，每次出栈，相当于要
     */
    class Solution {
        public int trap(int[] height) {
            int ans = 0;
            Deque<Integer> stack = new LinkedList<Integer>();
            int n = height.length;
            for (int i = 0; i < n; ++i) {
                while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                    int top = stack.pop();
                    if (stack.isEmpty()) {
                        break;
                    }
                    int left = stack.peek();
                    int currWidth = i - left - 1;
                    int currHeight = Math.min(height[left], height[i]) - height[top];
                    ans += currWidth * currHeight;
                }
                stack.push(i);
            }
            return ans;
        }
    }


    /**
     * 双指针，非常难想到
     * 一个从左到右，一个从右到左
     * 两个int分别维护从左到右和从右到左的最大值
     * 因为其实每个位置能接的雨水就是 min(左边最大值，右边最大值)
     * 比如左指针访问到当前点的时候，其实知道了左边最大值了，这时候如果右指针位置处右边的最大值已经比左边最大值大，那么当前左指针节点就只能有左边最大值那么多水了
     * 如果右边最大值比左边小呢?那么对于右节点来说，其可以接的水就只有右边最大值那么大了
     */
    class Solution2 {
        public int trap(int[] height) {
            int ans = 0;
            int left = 0, right = height.length - 1;
            int leftMax = 0, rightMax = 0;
            // mark:我很少用while，要注意学下，尤其是双指针
            while (left < right) {
                leftMax = Math.max(leftMax, height[left]);
                rightMax = Math.max(rightMax, height[right]);
                // 这个因果关系不好理解
                if (height[left] < height[right]) {
                    ans += leftMax - height[left];
                    ++left;
                } else {
                    ans += rightMax - height[right];
                    --right;
                }
            }
            return ans;
        }
    }

    class Solution3 {
        public int trap(int[] height) {
            int ans = 0;
            int left = 0, right = height.length - 1;
            int leftMax = 0, rightMax = 0;
            // mark:我很少用while，要注意学下，尤其是双指针
            while (left < right) {
                leftMax = Math.max(leftMax, height[left]);
                rightMax = Math.max(rightMax, height[right]);
                // 这里好理解，同我的注释，递推原因为，我每确定一个点能接雨水的值，我就能递推一个点
                if (leftMax < rightMax) {
                    ans += leftMax - height[left];
                    ++left;
                } else {
                    ans += rightMax - height[right];
                    --right;
                }
            }
            return ans;
        }
    }



    /**
     * 100, 比较简单。
     * 找到最大值, 然后从两边逼近这个最大值找出每个位置可以有的水量。
     */
    public int trap(int[] height) {
        if(height == null || height.length <= 2) return 0;
        int maxPosi = 0; // 记一下最大值的位置就行。
        for(int i = 0; i < height.length; i++){
            if(height[i] > height[maxPosi])
                maxPosi = i;
        }
        // 从两边逼近最大值
        int waterCount = 0;
        int tempMax = height[0];
        for(int i = 0; i < maxPosi; i++){
            if(height[i] > tempMax){
                tempMax = height[i];
            }else{
                waterCount += tempMax - height[i];
            }
        }
        tempMax = height[height.length - 1];
        for(int i = height.length - 1; i > maxPosi; i--){
            if(height[i] > tempMax){
                tempMax = height[i];
            }else{
                waterCount += tempMax - height[i];
            }
        }
        return waterCount;
    }
}
